package com.wdc.贪心;

@SuppressWarnings("ALL")
public class E03Leetcode53 {

    //暴力解法  还是有思想 就是java 超时了
//    public int maxSubArray(int[] nums) {
//        int result = Integer.MIN_VALUE;
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum = 0;
//            for (int j = i; j < nums.length; j++) {
//                sum += nums[j];
//                result = sum > result ? sum : result;
//            }
//
//        }
//        return result;
//    }

    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int result = Integer.MIN_VALUE;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            count += nums[i] ;
            result = Math.max(result,count);
            if (count <= 0 ){
                count = 0;
            }

        }
        return result;
    }



    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        E03Leetcode53 e03Leetcode53 = new E03Leetcode53();
        System.out.println(e03Leetcode53.maxSubArray(nums));
    }
}
